The present invention relates generally to digital communication systems and more particularly to a technique for providing enhanced performance. The discussion that follows assumes an understanding of digital communication principles as known to those of skill in that art. A good general reference in the digital communication field is John G. Proakis, Digital Communications, (McGraw-Hill 1995), herein incorporated by reference.
Conventional Viterbi Algorithm
The Viterbi algorithm accepts as input a sequence of received symbols and determines the maximum likelihood sequence of transmitted symbols. The Viterbi algorithm is applied to decode convolutional coding or trellis coding applied at the transmitter end or to remove the effects of a partial response channel. The algorithm is perhaps best understood by reference to a so-called trellis diagram. A trellis diagram is a time-indexed state diagram. At each trellis stage, n, there are two or more states. Transitions between states at a trellis stage, n, and states at a trellis stage n+1 denote transmitted symbols. A path through the trellis consists of a number of successive transitions and denotes a sequence of symbols. The number of states at each stage and the correspondence between transitions and symbols are particular to the relevant trellis code, convolutional code, or partial response channel characteristics. The Viterbi algorithm uses received symbol information to identify a particular path through the trellis and thus determine the maximum likelihood sequence of transmitted symbols.
Computation of the maximum likelihood sequence proceeds on a stage-by-stage basis. Possible paths are eliminated once it becomes clear they cannot be the maximum likelihood path. Given received symbol information, the likelihood of a particular branch being taken is evaluated according to a measure known as the branch metric. For each state, the Viterbi algorithm computes the branch metrics for the surviving paths leading to that state. The branch metric will typically consist of the previously accumulated branch metric for the path plus the branch metric for the transition taken to the new state. Based on the accumulated branch metrics for all the paths leading to the state, the Viterbi algorithm selects a best path to the state and eliminates the other states. Only one path survives to each stage, permitting identification of the maximum likelihood transmitted symbol sequence.
FIG. 2 depicts the prior art operation of a Viterbi decoding algorithm assuming channel phase is known. Consider an AWGN channel model, EQU r.sub.n =e.sup.j.crclbar. As.sub.n +w.sub.n, n=. . . 0,1,2, . . . ,(1)
where .crclbar. is channel phase; below we consider two cases where channel phase is known and where it is completely unknown. The transmitted symbol s.sub.n is an MPSK symbol, where s.sub.k =e.sup.j.crclbar.k, and .o slashed..sub.k is a uniformly distributed random phase taking values in {0,2.pi./M, . . . 2.pi.(M-1)/M}. The received sample is r.sub.n, and w.sub.n is an independent sample of zero mean white complex Gaussian noise of variance o.sup.2.
The mathematics of a conventional Viterbi decoding algorithm for a convolutional code, assuming channel phase .crclbar. is known will now be described. To simplify the description, assume the convolutional code has two branches into and out of each state. FIG. 2 depicts a state diagram wherein two states, u and v, at stage n-1, which both have a single branch into state w at stage n. Associated with state u is the previously determined winning path into state u, denoted by s.sub.u,0,s.sub.u,1, . . . s.sub.u,n-1, and a path metric m.sub.u. Associated with state v is the previously determined winning path into state v, denoted by s.sub.v,0,s.sub.v,1, . . . s.sub.v,n-1, and a path metric m.sub.v. Let s.sub.u,n be the symbol on the branch from state u to state w, and let s.sub.v,n be the symbol on the branch from state v to state w. Let s.sub.0,s.sub.1, . . . s.sub.n-1,s.sub.n be the first n actual transmitted symbols, and let r.sub.0,r1, . . . r.sub.n-1,r.sub.n be the corresponding received samples. The following discussion explains how to update state w at stage n, by finding the winning branch into state w, the winning path into state w, and the winning path metric for state w. The conventional Viterbi algorithm proceeds in four steps:
(1) Form two branch metrics EQU Re [r.sub.n s*.sub.u,n (s.sup.j.crclbar.)*], (2)
and EQU Re [r.sub.n s*.sub.v,n (s.sup.j.crclbar.)*]. (3)
(2) Use branch metric (2) to form a candidate path metric for the top path, EQU m.sub.u +Re [r.sub.n s*.sub.u,n (e.sup.j.crclbar.)*], (4)
and use branch metric (3) to form a candidate path metric for the bottom path, EQU m.sub.v +Re [r.sub.n s*.sub.v,n (e.sup.j.crclbar.)*]. (5)
(3) Compare (4) and (5) and select a winner, say (4).
(4) Update state w at stage n. The winning path into state w at stage n is s.sub.w,0,s.sub.w,1, . . . s.sub.w,n-1,s.sub.w,n where EQU (s.sub.w,0, s.sub.w,1, . . . s.sub.w,n-1,s.sub.w,n)=(s.sub.u,0,s.sub.u,1, . . . s.sub.u,n-1, s.sub.u,n).
The winning path metric is EQU m.sub.w =m.sub.u +Re [r.sub.n s*.sub.v,n (e.sup.j.crclbar.)*].
Non-coherent Viterbi Decoding Algorithm Operation
FIG. 3 depicts the prior art operation of a Viterbi decoding algorithm using multiple symbol noncoherent detection. Non-coherent Viterbi decoding is described in [9] A. N. D'Andrea, U. Mengali, and G. M. Vitetta, "Approximate ML decoding of coded PSK with no explicit carrier phase reference," IEEE Transactions on Communications, Vol. 42, no. 2/3/4, February/March/April 1994, pp. 1033-1039, incorporated herein by reference. This approach can be used without an explicit phase reference, and so assume that .crclbar. in (1) is uniformly distributed on (-.pi.,.pi.). FIG. 3 is the same as FIG. 2 except that each state has a path history variable associated with it; thus states u and v at stage n-1 have the path history variables W.sub.u,n-1 and W.sub.v,n-1, associated with them, respectively, where W.sub.u,n-1 and W.sub.v,n-1 are defmed by ##EQU1## and .alpha. is a real number in the range 0.ltoreq..alpha..ltoreq.1. For a particular state x, x .epsilon.{u,v}, the path history variable is a function of the winning path into state x, s.sub.x,0, s.sub.x,1, . . . s.sub.x,n-1, and the channel sample history r.sub.0, r.sub.1, . . . r.sub.n-1, r.sub.n ; the path history variable for a particular path acts as a remodulated phase reference for that path and takes the place of the coherent phase reference term (e.sup.j.crclbar.)* in steps (1)-(4) above.
The discussion will now turn to how to find the winning branch into state w at stage n, the winning path into state w, the winning path metric for state w, and the path history variable for state w at stage n, W.sub.w,n. The modified Viterbi algorithm proceeds in four steps:
(1a) Form two branch metrics EQU Re[r.sub.n s*.sub.u,n W*.sub.u,n-1 ], (6)
and EQU Re[r.sub.n s*.sub.v,n W*.sub.v,n-1 ]. (7)
(2a) Use branch metric (6) to form a candidate path metric for the top path , EQU m.sub.u +Re [r.sub.n s*.sub.u,n W*.sub.v,n-1 ], (8)
and use branch metric (7) to form a candidate path metric for the bottom path, EQU m.sub.v +Re [r.sub.n s*.sub.v,n W.sub.*.sub.v,n-1 ]. (9)
(3a) Compare (8) and (9) and select a winner, say (8).
(4a) Update state w at stage n. The winning path into state w at stage n is s.sub.w,0,s.sub.w,1, . . . s.sub.w,n-1, s.sub.w,n where EQU (s.sub.w,0,s.sub.w,1, . . . s.sub.w,n-1,s.sub.w,n)=(s.sub.u,0,s.sub.u,1, . . . s.sub.u,n-1, s.sub.u,n).
The winning path metric is EQU m.sub.w =m.sub.u +Re[r.sub.n s*.sub.u,n W*u,n-1].
The winning path history variable is EQU W.sub.w,n =r.sub.n s*.sub.u,n +.alpha.W.sub.u,n-1.
Note that steps (1a)-(4a) are very similar to steps (1)-(4), with the path history variable taking the place of the coherent phase reference term (e.sup.j.crclbar.)*.
Steps (1a)-(4a), illustrate one particular way of implementing trellis decoding with multiple symbol noncoherent detection. There are several other ways of implementing trellis decoding with multiple symbol noncoherent detection described in the literature which differ in how the branch metrics in (1a) are formed. However all approaches are fundamentally the same in that each branch metric in (1a) is formed using received samples and previous symbols along the winning path into that branch.
Problems of Digital Communication
The goal of digital communication is the error-free transmission of digital data over a transmission medium. To achieve this goal, there are various problems that the designer of digital communication equipment must overcome. One such problem is establishing phase and frequency synchronization between the receiver and the transmitter. Typically, analog tracking loops have been used to establish phase and frequency synchronization. The performance of these loops is affected phase slips and other problems. The non-coherent Viterbi decoding scheme described above represents a partial solution to the problem of phase synchronization in that the decoder does not need to know the phase shift introduced between the transmitter and receiver. However, this scheme is unsatisfactory in dealing with frequency offset as may be introduced by e.g., transmitter and receiver oscillators or Doppler shift arising in mobile communications.